English+GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Additionskette</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Additionskette</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Eine Additionskette für eine positive ganze Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist eine endliche <a href="Folge_(Mathematik)" title="Folge (Mathematik)">Folge</a> positiver ganzer Zahlen, die mit 1 beginnt und mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> endet und bei der jede Zahl der Folge außer der 1 die Summe zweier nicht notwendig verschiedener vorangegangener Folgenglieder ist. Für fast alle Fragestellungen genügt es, <a href="Monoton_steigende_Folge" class="mw-redirect" title="Monoton steigende Folge">streng monoton steigende</a> Folgen zu betrachten, so dass die Monotonie oft mit gefordert wird (siehe <a href="#Varianten_der_Definition">Varianten der Definition</a>).

Unter der Länge einer Additionskette versteht man die Anzahl der Folgenglieder, die Summe vorangegangener Folgenglieder sind – die 1 am Anfang wird also nicht mitgezählt. Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> die Länge der Additionskette <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a_{i})_{i=0,\cdots ,r}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a_{i})_{i=0,\cdots ,r}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4c8ae5282b5a0e74b5043a7bd9b0bb21e62309ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.321ex; height:3.009ex;" alt="{\displaystyle (a_{i})_{i=0,\cdots ,r}}" loading="lazy"> für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, so ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{0}=1,a_{1}=2,\cdots ,a_{r}=n}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{0}=1,a_{1}=2,\cdots ,a_{r}=n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6a65cc8a3184a3db00a00cffb2a0d13101a3c93c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:25.999ex; height:2.509ex;" alt="{\displaystyle a_{0}=1,a_{1}=2,\cdots ,a_{r}=n}" loading="lazy">. Die minimale Länge aller Additionsketten für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> wird mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8052b1c5d7efcba8ff9a4bd5e094416847f0e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.897ex; height:2.843ex;" alt="{\displaystyle l(n)}" loading="lazy"> bezeichnet.

Beispiel:

<ul><li>(1, 2, 4, 5, 9) ist eine Additionskette der Länge 4 für 9, denn 2 = 1+1, 4 = 2+2, 5 = 4+1 und 9 = 5+4.</li>

<li>(1, 2, 4, 6, 9) ist keine Additionskette für 9, denn 9 ist nicht Summe zweier vorangegangener Folgenglieder.</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(9)=4}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b421e5270d80bdce1187b4c5badb510aa2d38066.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.926ex; height:2.843ex;" alt="{\displaystyle l(9)=4}" loading="lazy">, denn es gibt keine kürzere Additionskette für 9. Andere Additionsketten für 9 sind gleich lang (zwei weitere) oder länger.

<div class="mw-heading mw-heading2"><h2 id="Anwendung_und_Geschichte">Anwendung und Geschichte</h2></div>

Die erste und bis heute wohl wichtigste Anwendung von Additionsketten ist die Optimierung der Berechnung von <a href="Potenz_(Mathematik)" title="Potenz (Mathematik)">Potenzen</a> mit großen <a href="Potenz_(Mathematik)#Natürliche_Exponenten" title="Potenz (Mathematik)">natürlichen Exponenten</a>. Hat man eine Additionskette der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> für eine positive ganze Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, so lässt sich zu einer Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> die Potenz <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2687184a7698e75db65a25bea7afd207bff3d03b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.448ex; height:2.343ex;" alt="{\displaystyle a^{n}}" loading="lazy"> durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> Multiplikationen berechnen. Sind nämlich für ein Glied <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> der Additionskette, das Summe vorangegangener Glieder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"> ist, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{y}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{y}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4a8db5dd8d21e536c50ae835a45006e5bdce1d52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.279ex; height:2.343ex;" alt="{\displaystyle a^{y}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{z}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{z}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6fda5d4b98ad1b1ded1a08a12990ef6f0e40316b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.231ex; height:2.343ex;" alt="{\displaystyle a^{z}}" loading="lazy"> schon berechnet worden, so ergibt sich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{x}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{x}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c031175c5142c25946f910813bf41c034fed75c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.402ex; height:2.343ex;" alt="{\displaystyle a^{x}}" loading="lazy"> daraus mit nur einer Multiplikation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{x}=a^{y+z}=a^{y}\cdot a^{z}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{x}=a^{y+z}=a^{y}\cdot a^{z}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a09ce52b6d182040a4d28789fe66528705009de3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:19.116ex; height:2.509ex;" alt="{\displaystyle a^{x}=a^{y+z}=a^{y}\cdot a^{z}}" loading="lazy">. Macht man das nacheinander für alle Glieder der Additionskette, so hat man mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> Multiplikationen den Wert von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2687184a7698e75db65a25bea7afd207bff3d03b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.448ex; height:2.343ex;" alt="{\displaystyle a^{n}}" loading="lazy"> erhalten. Dabei kann es sich bei der Basis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> um ein Element einer beliebigen nicht notwendig kommutativen <a href="Halbgruppe" title="Halbgruppe">Halbgruppe</a> handeln; es muss also keine Zahl im üblichen Sinne sein. Besonders für endliche Strukturen bietet sich das an, z. B. die Multiplikation und Potenzierung modulo einer ganzen Zahl in <a href="Restklassenring" title="Restklassenring">Restklassenringen</a>.

Die Frage, wie viele Multiplikationen man für eine Potenzierung mit einem natürlichen Exponenten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> mindestens braucht, ist 1894 in L'intermédiaire des mathématiciens von H. Dellac gestellt und im selben Jahr von <a href="Ernest_Jean_Philippe_Fauque_de_Jonqui%C3%A8res" title="Ernest Jean Philippe Fauque de Jonquières">Ernest de Jonquières</a> beantwortet worden, der für einige Fälle die Lösung angab.<a href="#cite_note-jonquieres-1">[1]</a>

Einen neuen Aufschwung hat das Problem durch die moderne Kryptographie genommen, wo bei einigen Verfahren hohe Potenzen ganzer Zahlen in <a href="Restklassenring" title="Restklassenring">Modulo-Arithmetik</a> gebraucht werden. Dabei kann die Berechnung durch geeignete Additionsketten beschleunigt werden. Die optimale Lösung zu berechnen, also eine kürzeste Addtionskette für eine Zahl zu finden, hat sich dabei als sehr schwierig erwiesen. Für die Praxis spielt das eine geringe Rolle, da auch fast optimale Lösungen den Zweck erfüllen, aber als mathematische Herausforderung ist es bis heute ein schwieriges Problem trotz der einfachen Fragestellung.

In kryptographischen Verfahren wie <a href="RSA-Kryptosystem" title="RSA-Kryptosystem">RSA</a> ist der Exponent Teil des privaten Schlüssels. Da die Anzahl der Rechenschritte von der Anzahl der Einsen in der Binärdarstellung des Exponenten abhängt, könnte ein Angreifer durch genaue Zeitmessung Rückschlüsse auf die Anzahl der binären Einsen und damit auf den Exponenten selbst ziehen. Um diesen <a href="Seitenkanalangriff" class="mw-redirect" title="Seitenkanalangriff">Seitenkanalangriff</a> zu vereiteln, wird das Potenzieren üblicherweise mit einem Algorithmus durchgeführt, dessen Laufzeit unabhängig von Exponenten ist.

<div class="mw-heading mw-heading2"><h2 id="Aufbau_von_Additionsketten">Aufbau von Additionsketten</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Varianten_der_Definition">Varianten der Definition</h3></div>

Die eingangs angegebene Definition einer Additionskette ist die ursprüngliche<a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a> und wird daher meist zugrunde gelegt. Bei ihr treten die Zahlen nicht notwendig in aufsteigender Reihenfolge auf; so sind etwa (1, 2, 3, 4, 8, 11), (1, 2, 4, 3, 8, 11) und (1, 2, 4, 8, 3, 11) drei verschiedene Additionsketten, die dieselben Summen derselben Glieder enthalten und sich nur in der Reihenfolge der Summenbildungen unterscheiden. In aller Regel interessiert man sich aber für die Reihenfolge nicht, sondern betrachtet die drei Ketten als Varianten derselben Kette, genauer: als <a href="%C3%84quivalenzrelation#Repräsentantensysteme" title="Äquivalenzrelation">Repräsentanten</a> derselben Äquivalenzklasse von Ketten. Diese ist dann allein durch die (ungeordnete) Menge der Glieder gegeben: Genau dann, wenn eine endliche Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> positiver ganzer Zahlen die Menge der Kettenglieder einer Additionskette (also die Bildmenge der Folge) ist, gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\in A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\in A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ab8d8b6750a18e1f23e2702ff86791e890438dd0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.746ex; height:2.176ex;" alt="{\displaystyle 1\in A}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\setminus \{1\}\subset \{x+y:x,y\in A\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\setminus \{1\}\subset \{x+y:x,y\in A\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe3d245208096a58f6888c30183d7538437e6fe1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.214ex; height:2.843ex;" alt="{\displaystyle A\setminus \{1\}\subset \{x+y:x,y\in A\}}" loading="lazy">. Dann aber ist insbesondere die eindeutig bestimmte streng monoton steigende, ab 0 indizierte Folge der Elemente von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> eine Additionskette für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=\max A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\max A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06c0b82055f02a230faa0b18a0ff5986329e5e72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.949ex; height:2.176ex;" alt="{\displaystyle n=\max A}" loading="lazy">. Es kann weitere Additionsketten für dieses <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> geben, die aus derselben Menge von Gliedern in anderer Reihenfolge bestehen; diese lassen sich aber leicht aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> konstruieren. Oft werden deshalb nur die streng monoton steigenden Additionsketten genauer untersucht, z. B. bei Knuth:<a href="#cite_note-4">[4]</a> „Wir können <a href="Ohne_Beschr%C3%A4nkung_der_Allgemeinheit" title="Ohne Beschränkung der Allgemeinheit">ohne Beschränkung der Allgemeinheit</a> annehmen, dass eine Additionskette aufsteigend ist, […] Von jetzt an werden wir nur aufsteigende Ketten betrachten, ohne diese Annahme explizit zu erwähnen.“

<div class="mw-heading mw-heading3"><h3 id="Aufzählung_von_Additionsketten">Aufzählung von Additionsketten</h3></div>

<th>5 (nur für 11)

</th></tr>

<tr>

<td rowspan="6">1

</td>

<td rowspan="6">1, 2

</td>

<td rowspan="3">1, 2, 3

</td>

<td rowspan="1">1, 2, 3, 4

</td>

<td>…, 5 | 6 | 7 | 8

</td>

<td>

</td>

<td>…, 7, 11 | 8, 11

</td></tr>

<tr>

<td rowspan="1">1, 2, 3, 5

</td>

<td>…, 6 | 7 | 8 | 10

</td>

<td>…, 10 , 15

</td>

<td>…, 6, 11 | 8, 11 | 10, 11

</td></tr>

<tr>

<td rowspan="1">1, 2, 3, 6

</td>

<td>…, 7 | 8 | 9 | 12

</td>

<td>…, 9, 15 | 12, 15

</td>

<td>…, 8, 11 | 9, 11

</td></tr>

<tr>

<td rowspan="3">1, 2, 4

</td>

<td rowspan="1">1, 2, 4, 5

</td>

<td>…, 6 | 7 | 8 | 9 | 10

</td>

<td>…, 10, 15

</td>

<td>…, 6, 11 | 7, 11 | 9, 11 | 10, 11

</td></tr>

<tr>

<td rowspan="1">1, 2, 4, 6

</td>

<td>…, 7 | 8 | 10 | 12

</td>

<td>

</td>

<td>…, 7, 11 | 10, 11

</td></tr>

<tr>

<td rowspan="1">1, 2, 4, 8

</td>

<td>…, 9 | 10 | 12 | 16

</td>

<td>

</td>

<td>…, 9, 11 | 10, 11

</td></tr></tbody></table>

In dieser Tabelle stehen alle Additionsketten der Länge bis 4 sowie eine Auswahl der insgesamt 135 Ketten der Länge 5, nämlich diejenigen, deren Endglied entweder 15 oder 11 ist. Der senkrechte Strich „|“ trennt alternative Teilketten. Das Auslassungszeichen „…“ bedeutet immer die Kette der Länge 3 in derselben Tabellenzeile. Die Endglieder sind fettgedruckt, wo sie in einer kürzesten Kette für diese Zahl erscheinen.

Auf diese Weise kann man im Prinzip alle Additionsketten aufzählen und erhält damit zu jeder Zahl eine kürzeste, alle kürzesten oder auch alle überhaupt. Ohne weiteres praktikabel ist dieses Verfahren aber nur für kleine Zahlen: Bereits mit der Länge 10 gibt es über 10 Millionen<a href="#cite_note-5">[5]</a> verschiedene Additionsketten, und ihre Zahl wächst rasch weiter.

Die Anfangsabschnitte einer kürzesten Kette sind nicht notwendig selbst kürzeste Ketten für ihr jeweiliges Endglied. So beginnen die Ketten für 7 und 11 in der obersten Tabellenzeile mit (1, 2, 3, 4), was keine kürzeste Kette ist. Es genügt also nicht, bei der Konstruktion von kürzesten Ketten für ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nur die kürzesten Ketten für die Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle <n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle <n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5b1f6b3c6d61796a08e0b48a0d65b3dde3cccdbc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.848ex; height:1.843ex;" alt="{\displaystyle <n}" loading="lazy"> heranzuziehen.

<div class="mw-heading mw-heading2"><h2 id="Kürzeste_Additionsketten">Kürzeste Additionsketten</h2></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></th>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0100f0a7c55506eb66f01a186b98e514563fd069.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.436ex; height:2.843ex;" alt="{\displaystyle \nu (n)}" loading="lazy"></th>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8052b1c5d7efcba8ff9a4bd5e094416847f0e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.897ex; height:2.843ex;" alt="{\displaystyle l(n)}" loading="lazy"></th>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d4ad18070e494503403daf39398e711c1378348e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.32ex; height:2.843ex;" alt="{\displaystyle g(n)}" loading="lazy"></th>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/45acf3d5914aa3ca6d1e328a7296f0c1ee805094.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.202ex; height:2.843ex;" alt="{\displaystyle b(n)}" loading="lazy"></th>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Lambda (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/763b9c503bc0ec2109ea1031a176850d169ea833.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.817ex; height:2.843ex;" alt="{\displaystyle \Lambda (n)}" loading="lazy">

</th></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>2

</td></tr>

<tr>

<td>2

</td></tr>

<tr>

<td>5

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>3

</td></tr>

<tr>

<td>4

</td></tr>

<tr>

<td>15

</td></tr>

<tr>

<td>3

</td></tr>

<tr>

<td>10

</td></tr>

<tr>

<td>14

</td></tr>

<tr>

<td>4

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>2

</td></tr>

<tr>

<td>7

</td></tr>

<tr>

<td>33

</td></tr>

<tr>

<td>6

</td></tr>

<tr>

<td>29

</td></tr>

<tr>

<td>40

</td></tr>

<tr>

<td>4

</td></tr>

<tr>

<td>4

</td></tr>

<tr>

<td>14

</td></tr>

<tr>

<td>24

</td></tr>

<tr>

<td>5

</td></tr>

<tr>

<td>23

</td></tr>

<tr>

<td>132

</td></tr>

<tr>

<td>12

</td></tr>

<tr>

<td>77

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>205

</td></tr>

<tr>

<td>173

</td></tr>

<tr>

<td>352

</td></tr>

<tr>

<td>1258

</td></tr>

<tr>

<td>471

</td></tr>

<tr>

<td>2661

</td></tr>

<tr>

<td>9787

</td></tr>

<tr>

<td>4

</td></tr>

<tr>

<td>6352

</td></tr>

<tr>

<td>2677

</td></tr>

<tr>

<td>129

</td></tr>

<tr>

<td>240

</td></tr>

<tr>

<td>934

</td></tr>

<tr>

<td>3960

</td></tr>

<tr>

<td>1072

</td></tr>

<tr>

<td>1

</td></tr></tbody></table>

Zu jeder <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlichen Zahl</a> ab 4 gibt es mehrere Additionsketten, die diese als letztes Element enthalten. Interessant sind besonders kürzeste Ketten, die eine bestimmte Zahl erreichen. Die <a href="Zweierpotenz" class="mw-redirect" title="Zweierpotenz">Zweierpotenzen</a> und die 3 – und nur diese, wie sich zeigen lässt – haben nur eine kürzeste Additionskette. Die 6 sowie alle Zahlen außer 9, die um 1 größer sind als eine Zweierpotenz ab 4, haben genau zwei kürzeste Additionsketten, z. B. 1, 2, 4, 8, 16, (17 oder 32), 33.

Die meisten Zahlen (letztlich sogar fast alle, bezogen auf die richtige Wahl einer Dichte) lassen sich mittels einer Additionskette beschreiben, deren Länge in Abhängigkeit von der Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> im Wesentlichen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}(n)+{\frac {\log _{2}(n)}{\log _{2}(\log _{2}(n))}}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}(n)+{\frac {\log _{2}(n)}{\log _{2}(\log _{2}(n))}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/58a41d0a4d91a78290d1a84ae7fbc524f50be4bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:23.972ex; height:6.509ex;" alt="{\displaystyle \log _{2}(n)+{\frac {\log _{2}(n)}{\log _{2}(\log _{2}(n))}}}" loading="lazy"> ist.

Eine vermutete und bisher bis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{64}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{64}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bb5d73f9701a025c1cc6c6a8ecc02c49d697fa8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.532ex; height:2.676ex;" alt="{\displaystyle n=2^{64}}" loading="lazy"> bestätigte untere Schranke für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8052b1c5d7efcba8ff9a4bd5e094416847f0e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.897ex; height:2.843ex;" alt="{\displaystyle l(n)}" loading="lazy"> ist

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n)=\lfloor \log _{2}(n)\rfloor +\lceil \log _{2}(\nu (n))\rceil }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5d030ad5bd8aa7ed1ac51e51d32f5f90d5021b14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.89ex; height:2.843ex;" alt="{\displaystyle g(n)=\lfloor \log _{2}(n)\rfloor +\lceil \log _{2}(\nu (n))\rceil }" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nu (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0100f0a7c55506eb66f01a186b98e514563fd069.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.436ex; height:2.843ex;" alt="{\displaystyle \nu (n)}" loading="lazy"> die Anzahl der Einsen in der <a href="Dualsystem" title="Dualsystem">Binärdarstellung</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist. Das ist zugleich mindestens für kleine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> eine brauchbare Schätzung für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8052b1c5d7efcba8ff9a4bd5e094416847f0e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.897ex; height:2.843ex;" alt="{\displaystyle l(n)}" loading="lazy">: bis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=3690}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=3690}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4aacf471ca7b4f80964b965a8a6a235e0f41afa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.143ex; height:2.176ex;" alt="{\displaystyle n=3690}" loading="lazy"> ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8052b1c5d7efcba8ff9a4bd5e094416847f0e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.897ex; height:2.843ex;" alt="{\displaystyle l(n)}" loading="lazy"> entweder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d4ad18070e494503403daf39398e711c1378348e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.32ex; height:2.843ex;" alt="{\displaystyle g(n)}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n)+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n)+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b392817649fe3d1b03671cca03c29846495413e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.323ex; height:2.843ex;" alt="{\displaystyle g(n)+1}" loading="lazy">, und bis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{31}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{31}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6c1f5044e577539852e3eaff08f9091345c9554d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.532ex; height:2.676ex;" alt="{\displaystyle n=2^{31}}" loading="lazy"> ist mit nur einer Ausnahme <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leqq l(n)-g(n)\leqq 3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leqq l(n)-g(n)\leqq 3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d1878454f228c8485785e933769513fc072efe69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.58ex; height:2.843ex;" alt="{\displaystyle 0\leqq l(n)-g(n)\leqq 3}" loading="lazy">. Die Ausnahme ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2135101487\approx 0.994\cdot 2^{31}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2135101487\approx 0.994\cdot 2^{31}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0214321c4984544c07f0c5fdb96e8234daf65928.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:29.231ex; height:2.676ex;" alt="{\displaystyle n=2135101487\approx 0.994\cdot 2^{31}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nu (n)=16}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu (n)=16}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/edaf7e65d5af3a5bba2bc6dc91ad57beb98ef9b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.86ex; height:2.843ex;" alt="{\displaystyle \nu (n)=16}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n)=34}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n)=34}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6c55d8d89214081e2cc9c69765b4bf59e5f05e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.743ex; height:2.843ex;" alt="{\displaystyle g(n)=34}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)=38}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)=38}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec991e79b07cb799034a7b42a70e73c6ca37fd14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.321ex; height:2.843ex;" alt="{\displaystyle l(n)=38}" loading="lazy">.

Eine obere Schranke für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8052b1c5d7efcba8ff9a4bd5e094416847f0e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.897ex; height:2.843ex;" alt="{\displaystyle l(n)}" loading="lazy"> ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b(n)=\lfloor \log _{2}(n)\rfloor +\nu (n)-1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b(n)=\lfloor \log _{2}(n)\rfloor +\nu (n)-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6caaf73cecbad68a4077545962480d8e67b206dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.874ex; height:2.843ex;" alt="{\displaystyle b(n)=\lfloor \log _{2}(n)\rfloor +\nu (n)-1}" loading="lazy">, denn man kann zunächst die Kette aller Zweierpotenzen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leqq n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \leqq n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f029f4d85c55db1918f5e066a5ba4a2ff6ce663e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.848ex; height:2.676ex;" alt="{\displaystyle \leqq n}" loading="lazy"> bilden und dann die übrigen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nu (n)-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu (n)-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0e83a2d26a9e160a6c9d7140e85834f04bb06e97.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.439ex; height:2.843ex;" alt="{\displaystyle \nu (n)-1}" loading="lazy"> in der Binärdarstellung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> enthaltenen Zweierpotenzen durch Addition hinzufügen. Einige Beispiele von Werten dieser Funktionen sind in der Tabelle rechts aufgeführt, dazu die Anzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Lambda (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Lambda (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/763b9c503bc0ec2109ea1031a176850d169ea833.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.817ex; height:2.843ex;" alt="{\displaystyle \Lambda (n)}" loading="lazy"> kürzester Ketten für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.

Für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nu (n)<5}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu (n)<5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9c7a7ab09cc3e19c8c6622bcd5c46fbb4bcd5490.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.697ex; height:2.843ex;" alt="{\displaystyle \nu (n)<5}" loading="lazy"> ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8052b1c5d7efcba8ff9a4bd5e094416847f0e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.897ex; height:2.843ex;" alt="{\displaystyle l(n)}" loading="lazy"> bekannt<a href="#cite_note-6">[6]</a>:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu (n)<4}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/284f4e7dd58af7ef850991802c3cef4d21307ae4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.697ex; height:2.843ex;" alt="{\displaystyle \nu (n)<4}" loading="lazy">, so ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)=b(n)=g(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)=b(n)=g(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3ceccf024072ec7aceb4c4a1f23933543425f5c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.616ex; height:2.843ex;" alt="{\displaystyle l(n)=b(n)=g(n)}" loading="lazy">.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu (n)=4}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3dce48ab10a81969b532e71f857a4cb4406203da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.697ex; height:2.843ex;" alt="{\displaystyle \nu (n)=4}" loading="lazy">, d. h. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{p}+2^{q}+2^{r}+2^{s}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{p}+2^{q}+2^{r}+2^{s}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc0fa64f1f53ea9ee42a88953d5299b9d724b2e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:21.689ex; height:2.509ex;" alt="{\displaystyle n=2^{p}+2^{q}+2^{r}+2^{s}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p>q>r>s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p>q>r>s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dc180e23c51fcc54cd4d03a5b4a16843bb1847ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:13.763ex; height:2.176ex;" alt="{\displaystyle p>q>r>s}" loading="lazy">, so definieren wir <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=2^{p-q}+1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=2^{p-q}+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dd1fbeb0ba8295cd5731b41b958da30f024ae2f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.365ex; height:2.676ex;" alt="{\displaystyle c=2^{p-q}+1}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=2^{r-s}+1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=2^{r-s}+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0b669c72447c138a358f2b90d46f8518f542165d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.503ex; height:2.676ex;" alt="{\displaystyle d=2^{r-s}+1}" loading="lazy">. Ist dann <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\geqq d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\geqq d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9dc9f4697319286d94a85b6d57e4d2dcc55d8180.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.321ex; height:2.676ex;" alt="{\displaystyle c\geqq d}" loading="lazy"> und gibt es eine kürzeste Additionskette für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">, in der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> vorkommt, so ergibt sich daraus eine Additionskette für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)=p+2=g(n)=b(n)-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)=p+2=g(n)=b(n)-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/49077a13c9cf480a2084c9d4723e0456700f80cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.889ex; height:2.843ex;" alt="{\displaystyle l(n)=p+2=g(n)=b(n)-1}" loading="lazy">. Das ist genau dann der Fall, wenn

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d8498d2878942ddeef7d6a8ec870959f0d38d32e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.321ex; height:2.176ex;" alt="{\displaystyle c=d}" loading="lazy"> (Beispiel: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=45,c=d=5}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=45,c=d=5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cee05d23272b49844293a9a4960f1e93eb68c748.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.434ex; height:2.509ex;" alt="{\displaystyle n=45,c=d=5}" loading="lazy">, Kette 1, 2, 4, 5, 10, 20, 40, 45 der Länge 7) oder</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=2d-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b375f2ee642accc0f5a7567bddfe29e3d74aea27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.486ex; height:2.343ex;" alt="{\displaystyle c=2d-1}" loading="lazy"> (Beispiel: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=23,c=5,d=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=23,c=5,d=3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c8bff82e8189152acd9a4caff5768f425fa62a1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.631ex; height:2.509ex;" alt="{\displaystyle n=23,c=5,d=3}" loading="lazy">, Kette 1, 2, 3, 5, 10, 20, 23 der Länge 6) oder</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=9,d=3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9ef1a901c401296908e1d7d092747ccc0affad0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.778ex; height:2.509ex;" alt="{\displaystyle c=9,d=3}" loading="lazy"> (Beispiel: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=147}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=147}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/99cdc5875122494ee8233236f505dd5a4b280a98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.981ex; height:2.176ex;" alt="{\displaystyle n=147}" loading="lazy">, Kette 1, 2, 3, 6, 9, 18, 36, 72, 144, 147 der Länge 9).</li></ul></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> die Form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 135\cdot 2^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 135\cdot 2^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cfd03b7453df9ad3675e5f027d67b24c3ca0a7e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.418ex; height:2.676ex;" alt="{\displaystyle 135\cdot 2^{k}}" loading="lazy">, mithin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nu (n)=4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu (n)=4}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3dce48ab10a81969b532e71f857a4cb4406203da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.697ex; height:2.843ex;" alt="{\displaystyle \nu (n)=4}" loading="lazy">, so ist 1, 2, …, 45, 90, 135, …, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {n}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/30bcb00be91a9d9c490e21d7ce09631eeef03365.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.657ex; height:1.676ex;" alt="{\displaystyle {\boldsymbol {n}}}" loading="lazy"> eine Kette der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)=k+9=g(n)=b(n)-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)=k+9=g(n)=b(n)-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/35a4b2f317b534565e4763e6387424883ca2f483.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.931ex; height:2.843ex;" alt="{\displaystyle l(n)=k+9=g(n)=b(n)-1}" loading="lazy">.</li>

<li>In allen anderen Fällen mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nu (n)=4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nu (n)=4}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3dce48ab10a81969b532e71f857a4cb4406203da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.697ex; height:2.843ex;" alt="{\displaystyle \nu (n)=4}" loading="lazy"> ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(n)=b(n)=g(n)+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(n)=b(n)=g(n)+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5a093e418bd8f8dd7625ce16f703f4e377b4d270.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.619ex; height:2.843ex;" alt="{\displaystyle l(n)=b(n)=g(n)+1}" loading="lazy">.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html">Shortest Addition Chains</a> Ergebnisse und Literaturverweise zusammengestellt von Achim Flammenkamp</li>

<li><a rel="nofollow" class="external text" href="https://oeis.org/">Online-Encyclopedia of Integer Sequences</a>, insbesondere Folgen <a rel="nofollow" class="external text" href="https://oeis.org/A003313">A003313</a> und <a rel="nofollow" class="external text" href="https://oeis.org/A079300">A079300</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-jonquieres-1"><a href="#cite_ref-jonquieres_1-0">↑</a> Frage 49 und Antwort dazu in L'intermédiaire des mathématiciens, Band 1 (1894), S. 20 und 162–164; <a rel="nofollow" class="external text" href="http://gdz.sub.uni-goettingen.de/dms/load/toc/?PID=PPN599473517_0001">Digitalisat online</a> bei der SUB Göttingen

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> <a href="Arnold_Scholz" title="Arnold Scholz">Arnold Scholz</a>: <cite style="font-style:italic">(Aufgabe 253)</cite>. In: <cite style="font-style:italic"><a href="Jahresbericht_der_Deutschen_Mathematiker-Vereinigung" class="mw-redirect" title="Jahresbericht der Deutschen Mathematiker-Vereinigung">Jahresbericht der Deutschen Mathematiker-Vereinigung</a></cite>. Band 47, 1937, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220012-0456%22&key=cql">0012-0456</a>, S. 41–42 (<a rel="nofollow" class="external text" href="http://www.digizeitschriften.de/download/PPN37721857X_0047/PPN37721857X_0047___log34.pdf">digizeitschriften.de</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Additionskette&rft.atitle=%28Aufgabe+253%29&rft.au=Arnold+Scholz&rft.date=1937&rft.genre=journal&rft.issn=0012-0456&rft.jtitle=Jahresbericht+der+Deutschen+Mathematiker-Vereinigung&rft.pages=41-42&rft.volume=47" style="display:none">

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> <a href="Alfred_Brauer" class="mw-redirect" title="Alfred Brauer">Alfred Brauer</a>: <cite class="lang" lang="en" dir="auto" style="font-style:italic">On Addition Chains</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="Bulletin_of_the_American_Mathematical_Society" title="Bulletin of the American Mathematical Society">Bulletin of the American Mathematical Society</a></cite>. Band 45, 1939, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220273-0979%22&key=cql">0273-0979</a>, S. 736–739 (englisch, <a rel="nofollow" class="external text" href="https://www.ams.org/journals/bull/1939-45-10/S0002-9904-1939-07068-7/S0002-9904-1939-07068-7.pdf">ams.org</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Additionskette&rft.atitle=On+Addition+Chains&rft.au=Alfred+Brauer&rft.date=1939&rft.genre=journal&rft.issn=0273-0979&rft.jtitle=Bulletin+of+the+American+Mathematical+Society&rft.pages=736-739&rft.volume=45" style="display:none">

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> Donald E. Knuth: <cite style="font-style:italic">Arithmetik</cite>. Springer, Berlin, Heidelberg u. a. 2001, ISBN 3-540-66745-8, S. 298 (englisch: <cite class="lang" lang="en" dir="auto" style="font-style:italic">The Art of Computer Programming</cite>. Übersetzt von R. Loos).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Additionskette&rft.au=Donald+E.+Knuth&rft.btitle=Arithmetik&rft.date=2001&rft.genre=book&rft.isbn=3540667458&rft.pages=298&rft.place=Berlin%2C+Heidelberg+u.+a.&rft.pub=Springer" style="display:none">  Komplettes Zitat: „Wir können ohne Beschränkung der Allgemeinheit annehmen, dass eine Additionskette aufsteigend ist, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1=a_{0}<a_{1}<\cdots <a_{r}=n}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1=a_{0}<a_{1}<\cdots <a_{r}=n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d38f9269b75a660f4df1fcfb5ab6c471fea37c1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:27.544ex; height:2.509ex;" alt="{\displaystyle 1=a_{0}<a_{1}<\cdots <a_{r}=n}" loading="lazy">. Denn wenn irgend zwei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> gleich sind, kann eines von ihnen weggelassen werden; und wir können auch die Folge (1) in aufsteigender Ordnung neu arrangieren und Terme <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle >n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle >n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/33306195204206fc57a73e1618c55b20803f3e88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.848ex; height:1.843ex;" alt="{\displaystyle >n}" loading="lazy"> wegnehmen, ohne die Additionsketteneigenschaft (2) zu zerstören. Von jetzt an werden wir nur aufsteigende Ketten betrachten, ohne diese Annahme explizit zu erwähnen.“

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> Folge <a href="https://oeis.org/A008933" class="extiw external" title="oeis:A008933">A008933</a> in <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">↑</a> Donald E. Knuth: The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 2nd Ed. 1981, Addison-Wesley, ISBN 0-201-03822-6, Theorem C, S. 449

</li>

</ol>

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-01-29" href="https://de.wikipedia.org/wiki/?title=Additionskette&oldid=252811202">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>